/**
 * 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。


堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：


1.创建一个堆H[0..n-1]
2.把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4. 重复步骤2，直到堆的尺寸为1
 */


(function () {
    // 堆排序  
    var h = [],// 用来存放堆的数组  
        n;// 用来存储堆中元素的个数，也就是堆的大小  
    // 交换函数，交换堆中两个元素的值  
    function swap(x, y) {
        var t;
        t = h[x];
        h[x] = h[y];
        h[y] = t;
    }
    // 向下调整函数  
    function siftdown(i) {
        // 传入一个需要向下调整的节点编号i，这里传入1，即从堆的定点开始向下调整  
        var flag = 0,// flag用来标记是否需要继续向下调整  
            t;
        // 当i节点有儿子（其实至少有左儿子）并且需要继续调整的时候循环就执行  
        while (i * 2 <= n && flag === 0) {
            // 首先判断它和左儿子的关系，并用t记录值较小的节点编号  
            var leftChildIndex = i * 2 + 1,
                rightChildIndex = i * 2 + 2;
            if (h[i] > h[leftChildIndex]) {
                t = leftChildIndex;
            } else {
                t = i;
            }
            // 如果它有右儿子，在对右儿子进行讨论  
            if (rightChildIndex <= n) {
                // 如果右儿子的值更小，更新较小的节点编号  
                if (h[t] > h[rightChildIndex]) {
                    t = rightChildIndex;
                }
            }

            // 如果发现最小的节点编号不是自己，说明子节点中有比父节点更小的  
            if (t !== i) {
                swap(t, i);// 交换他们  
                i = t;// 更新i为刚才与他交换的儿子节点的编号，便于接下来继续向下调整  
            } else {
                flag = 1;
            }
        }
    }

    // 建立堆的函数  
    function create() {
        var i;
        // 从最后一个非叶节点到第一个节点依次进行向上调整  
        for (i = n / 2; i >= 0; i--) {
            siftdown(i);
        }
        console.error(h);
    }

    // 删除最大的元素  
    function deleteMax() {
        var t;
        t = h[0];// 用一个临时变量记录堆顶点的值  
        console.info(t);
        h[0] = h[n];// 将堆最后一个点赋值到堆顶  
        n--;// 堆的元素数减1  
        siftdown(0);// 向下调整(相当于重建堆)  
        return t;
    }
    function sort(ary) {
        h = ary;
        var num = ary.length,
            i;
        n = num - 1;
        // 建堆  
        create();
        var sortedAry = [];
        for (i = 0; i <= num; i++) {
            sortedAry.push(deleteMax());
        }
        return sortedAry;
    }
    console.log(sort(ConstArr["10000"]));// [5, 7, 17, 22, 36, 46, 46]   

})();